package seqlist.LeetCode;
//25. K 个一组翻转链表
/**
 * k 是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */

/**
 *
 */
public class Num25_reverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode();
        ListNode prve = dummyHead;//前驱

        while(head != null){
            int conut = 0;
            //检查是否具有翻转资格
            ListNode node = head;
            while(node != null && conut < k){
                conut ++;
                node = node.next;
            }

            if(conut == k){
              prve.next = reverseBetween(head,1,k);

              for (int i = 0; i < k; i++){
                    prve = prve.next;
              }

            }


            head = node;

        }

        return dummyHead.next;
    }

    //翻转 left 到 right 之间链表
    public ListNode reverseBetween(ListNode head, int left, int right) {

        //当链表为空或者 只有一个是时候，就不需要翻转链表了
        if(head == null || head.next == null){
            return head;
        }

        ListNode dummyHead = new ListNode();
        ListNode prve = dummyHead;
        dummyHead.next = head;

        //寻找left - 1次找到前驱位置
        for (int i = 0; i < left - 1; i++) {
            prve = prve.next;
        }//出来后此时的prve就是待翻转节点的前驱了

        ListNode node = prve.next;
        //需要翻转的次数是 right - left
        for (int i = 0; i < right - left; i++) {
            ListNode cur = node.next;//待翻转的节点
            node.next = cur.next;//跳过待翻转的节点连接下一个节点地址
            cur.next = prve.next;//头插
            prve.next = cur;//更新头插节点地址
        }
        return dummyHead.next;
    }

}
